﻿//#define WR

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.InteropServices;

using alib;
using alib.Character;
using alib.String;
using alib.IO;
using alib.Enumerable;
using alib.Concurrency;
using alib.Collections;
using alib.Collections.ReadOnly;
using alib.Debugging;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public unsafe sealed class DerivationStore : identity_base, IIdentList<IDerivation>
	{
		public DerivationStore(Grammar g)
			: base(g)
		{
			this.g = g;
		}

		//public IEnumerable<IDerivation> AddDerivations(IEnumerable<IDerivation> ie)
		//{
		//    if (buf != null)
		//        throw new Exception("can only add derivations once.");
		//    return new _build_helper().go(this, ie);
		//}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		readonly Grammar g;

		EntryMgr em { get { return g.em; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		byte[] buf;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int c_nodes;

		//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		//int c_tops;
		public int Count { get { throw new Exception(); } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int c_roots;
		public int RootCount { get { return c_roots; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int c_redirects;


		public int _count_tops()
		{
			int _c = 0;
			if (buf != null)
				fixed (byte* pb = buf)
				{
					dnode* pt = (dnode*)pb;
					while ((byte*)pt < pb + buf.Length)
					{
						_c++;
						int nest = 1;
						do
						{
							nest += pt->arity - 1;
							dnode.Next(ref pt);
						}
						while (nest > 0);
					}
				}
			return _c;
		}

		byte[] SafeBuf
		{
			get
			{
				var _buf = this.buf;
				if (_buf == null)
				{
					if (bld == null)
						throw new Exception();
					_buf = bld.SoFar;
				}
				return _buf;
			}
		}

		Builder bld = null;
		public IDerivation _get(uint offs)
		{
			dnode.flags nf = dnode.get_obj_type((dnode.flags)SafeBuf[offs]);

			if ((nf & dnode.flags.Redirect) != 0)
				throw new Exception(String.Format("XX {0} {1:X2}", nf, (byte)nf));


			_cdrv_base d;
#if CACHE
			_cdrv_base d_prev;
			d= _find_cached(offs, out d_prev);
#else
			d = null;
#endif
			if (d == null)
			{
				if (nf == dnode.flags.RootMatches)
					d = new _cdrv_rootmatches(this, offs);
				else if (nf == dnode.flags.RootMatch)
					d = new _cdrv_rootmatch(this, offs);
				else if (nf == dnode.flags.LexicalEntry)
					d = new _cdrv_lexent(this, offs);
				else
					d = new _cdrv_base(this, offs);
#if CACHE
				_add_to_cache(d_prev, d);
#endif
			}
			return d;
		}

#if CACHE
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// MRU cache of rendered derivations, in order to curb TFS reconstitution work
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		_cdrv_base first;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int global_access = 0;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		Object cache_lock = new Object();

		_cdrv_base _find_cached(uint offs, out _cdrv_base d_prev)
		{
			var cur = first;
			d_prev = null;
			while (cur != null && cur.offs <= offs)
			{
				if (cur.offs == offs)
				{
					cur.last_access = global_access++;
					return cur;
				}
				d_prev = cur;
				cur = cur.next;
			}
			return null;
		}

		void _add_to_cache(_cdrv_base prev, _cdrv_base cur)
		{
			cur.last_access = global_access++;
			uint offs = cur.offs;
			lock (cache_lock)
			{
			retry:
				if (prev == null && first != null && first.offs < offs)
				{
					if (_find_cached(offs, out prev) != null)
						return;
					if (prev == null && first != null)
						throw new Exception();
				}

				if (prev == null)
				{
					cur.next = first;
					first = cur;
					return;
				}

				_cdrv_base pn;
				if (prev.offs == offs || ((pn = prev.next) != null && pn.offs == offs))
					return;

				if (prev.offs > offs || (pn != null && pn.offs < offs))
					if (_find_cached(offs, out prev) != null)
						return;
					else
						goto retry;

				cur.next = pn;
				prev.next = cur;
			}
		}

		public void clear_cache()
		{
			first = null;
		}

		IEnumerable<IDerivation> cache()
		{
			for (var cur = first; cur != null; cur = cur.next)
				yield return cur;
		}
#endif
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// recover the immediate daughter derivation tokens (if any) for this derivation token. 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		uint[] _dtr_finder(uint offs)
		{
			int arity = dnode._get_arity(this, offs);
#if DEBUG
			if (arity == 0)
				throw new Exception();
#endif
			uint[] dtrs = new uint[arity];
			var _buf = SafeBuf;
			fixed (byte* pb = _buf)	// note: using 'pb' true base as r-value below. so don't pre-offset.
			{
				dnode* pt = (dnode*)(pb + offs);
				dnode.Next(ref pt);
				int i_dtr = 0;
				while (true)
				{
					uint f = *(uint*)pt;
					dtrs[i_dtr++] = ((dnode.flags)f & dnode.flags.Redirect) != 0 ?
										(uint)(f >> 8) :
										(uint)((byte*)pt - pb);
					if (i_dtr == arity)
						break;
					int nest = 1;
					do
					{
						nest += pt->arity - 1;
						dnode.Next(ref pt);
					}
					while (nest > 0);
				}
			}
			return dtrs;
		}

		IEnumerable<uint> top_nodes()
		{
			if (buf == null)
				yield break;
			uint offs = 0;
			while (offs < buf.Length)
			{
				yield return offs;
				int nest = 1;
				do
					nest += _node_info(ref offs);
				while (nest > 0);
			}
		}

		int _node_info(ref uint offs)
		{
			fixed (byte* pb = &SafeBuf[offs])
			{
				offs += (uint)((dnode*)pb)->record_size;
				return ((dnode*)pb)->arity - 1;
			}
		}

		public IDerivation this[int index]
		{
			get
			{
				using (var e = top_nodes().GetEnumerator())
				{
					for (int i = 0; i <= index; i++)
						e.MoveNext();
					return _get(e.Current);
				}
			}
			set { throw not.impl; }
		}

		public IEnumerator<IDerivation> GetEnumerator()
		{
			using (var e = top_nodes().GetEnumerator())
				while (e.MoveNext())
					yield return _get(e.Current);
		}

		IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
		public int IndexOf(IDerivation item) { throw not.impl; }
		public bool Contains(IDerivation item) { throw not.impl; }
		public void CopyTo(IDerivation[] array, int arrayIndex)
		{
			foreach (uint offs in top_nodes())
				array[arrayIndex++] = _get(offs);
		}

#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		_cdrv_base[] _dbg_nodes { get { return top_nodes().Select(offs => (_cdrv_base)_get(offs)).ToArray(); } }
#endif

		void ICollection.CopyTo(Array array, int index) { throw not.impl; }
		bool ICollection.IsSynchronized { get { return false; } }
		object ICollection.SyncRoot { get { return this; } }

		public override String ToString()
		{
			int cb = buf != null ? buf.Length : 0;
			return String.Format("{0} nodes {1} tops ({2} bytes)", c_nodes, Count, cb);
		}

		public static Builder New(Grammar g)
		{
			DerivationStore ds = new DerivationStore(g);
			ds.bld = new Builder(ds);
			return ds.bld;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class Builder
		{
			public DerivationStore ds;
			int c_nodes, c_redirects;
			Dictionary<IDerivation, uint> stored = new Dictionary<IDerivation, uint>();
			List<uint> roots = new List<uint>();
			BinaryWriter bw;

			public Builder(DerivationStore ds)
			{
				this.ds = ds;
				this.bw = new BinaryWriter(new MemoryStream());
			}

			public IDerivation AddDerivation(IDerivation hint, IReadOnlyList<IDerivation> dtrs)
			{
				uint offs = _write(hint, dtrs);

				if (dnode._f_redirect(ds, offs))
					throw new Exception();

				return ds._get(offs);
			}

			uint _write(IDerivation hint, IReadOnlyList<IDerivation> dtrs)
			{
				uint offs;

				// check the utility of the hint
				int dtr_arity = dtrs.Count;
				if (dtr_arity == 0)
					goto not_same;

				if (hint is _cdrv_base)
					offs = ((_cdrv_base)hint).offs;
				else if (!stored.TryGetValue(hint, out offs))
				{
					stored.Add(hint, (uint)bw.BaseStream.Position);
					goto not_same;
				}

				var x1 = ds._dtr_finder(offs);
				int i = 0;
				foreach (var z in dtrs)
				{
					var zz = z as _cdrv_base;
					if (zz == null || zz.offs != x1[i++])
						goto not_same;
				}

				bw.Write((uint)dnode.flags.Redirect | ((uint)offs << 8));
				c_redirects++;
				return offs;

			not_same:
				offs = (uint)bw.BaseStream.Position;

				dnode.Write(bw, hint);
				if (hint.IsValidRoot())
					roots.Add(offs);
				c_nodes++;
				if (dtrs == null)
					throw new Exception();// dtrs = d.Daughters;
				if (dtr_arity != 0)
					foreach (var dd in dtrs)
						_write(dd, dd.Daughters);
				return offs;
			}

			public byte[] SoFar { get { return ((MemoryStream)bw.BaseStream).GetBuffer(); } }

			public IList<IDerivation> Close()
			{
				ds.bld = null;
				MemoryStream ms = (MemoryStream)bw.BaseStream;
				var buf = ds.buf = ms.GetBuffer();
#if false
				if (ms.Position < buf.Length)
				{
					buf = new byte[ms.Position];
					Array.Copy(ds.buf, buf, ms.Position);
					ds.buf = buf;
				}
#endif
				//Console.WriteLine(buf.Length);
				bw.Close();

				ds.c_nodes = c_nodes;
				ds.c_redirects = c_redirects;
				ds.c_roots = roots.Count;

				//#if DEBUG
				//                int q = ds._count_tops();
				//                Debug.Assert(ds.c_tops == q);
				//#endif
				IList<IDerivation> lr;
				lr = ds.c_roots == 0 ?
								Collection<IDerivation>.None :
								(IList<IDerivation>)new _list_realizer<IDerivation>(ds, roots);

				ms = null;
				bw = null;
				stored = null;
				roots = null;
				ds = null;
				return lr;
			}
		};

#if false
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		struct _build_helper
		{
			BinaryWriter bw;
			int c_nodes, c_redirects;
			Dictionary<IDerivation, uint> stored;

			public IList<IDerivation> go(DerivationStore ds, IEnumerable<IDerivation> ie)
			{
				uint[] arr = new uint[ds.c_tops = ((ICollection)ie).Count];
				stored = new Dictionary<IDerivation, uint>();

				using (MemoryStream ms = new MemoryStream())
				using (bw = new BinaryWriter(ms))
				{
					int i = 0;
					foreach (var d in ie)
					{
						arr[i++] = (uint)bw.BaseStream.Position;
						_write(d);
					}

					var buf = ds.buf = ms.GetBuffer();
					if (ms.Position < buf.Length)
					{
						buf = new byte[ms.Position];
						Array.Copy(ds.buf, buf, ms.Position);
						ds.buf = buf;
					}
					ds.c_nodes = c_nodes;
					ds.c_redirects = c_redirects;
					Debug.Assert(ds.c_tops == ds._count_tops());
					return new _list_realizer(ds, arr);
				}
			}

			void _write(IDerivation d)
			{
				uint offs;
				if (stored.TryGetValue(d, out offs))
				{
					bw.Write(offs);
					c_redirects++;
				}
				else
				{
					offs = ((uint)dnode.flags.Redirect | ((uint)bw.BaseStream.Position << 8));
					stored.Add(d, offs);
					dnode.Write(bw, d);
					c_nodes++;
					var dtrs = d.Daughters;
					int dtr_arity = dtrs.Count;
					if (dtr_arity != 0)
						for (int i = 0; i < dtr_arity; i++)
							_write(dtrs[i]);
				}
			}
		};
#endif
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		[StructLayout(LayoutKind.Explicit)]
		struct dnode
		{
			[FieldOffset(0)]
			uint flags_arity_id;

			[FieldOffset(4)]
			public int seq_id;
			// [8...


			[Flags]
			public enum flags : byte
			{
				_EntryTypeMask /*	*/	= 0x03,
				Rule /*				*/	= 0x01,
				Lexical /*			*/	= 0x02,
				LexicalRule /*		*/	= Lexical | Rule,
				LexicalEntry /*		*/	= Lexical,
				LexicalEntryGeneric /**/= Lexical | Spanning,
				SyntaxRule /*		*/	= Rule,

				Spanning /*			*/	= 0x04,
				RootMatch /*		*/	= 0x08,
				RootMatches /*		*/	= 0x10,
				Validated /*		*/	= 0x20,

				Redirect /*			*/	= 0x40,
			};

			[StructLayout(LayoutKind.Explicit)]
			struct rootmatch
			{
				[FieldOffset(0)]
				dnode _header;
				[FieldOffset(8)]
				public int ss_id;
				// [12...
			};

			[StructLayout(LayoutKind.Explicit)]
			struct rootmatches
			{
				[FieldOffset(0)]
				rootmatch _header;
				[FieldOffset(8)]
				public int c_rm;
			};

			[StructLayout(LayoutKind.Explicit)]
			struct redirect
			{
				[FieldOffset(0)]
				int redir_flag_offs;
			};

			static int _make_fid(IDerivation d)
			{
				int fid;
				IChartLicense ent = d.ChartLicense;
				if (ent is LexicalEntry && !(ent is GenericLexicalEntry))
					fid = ((int)ent.Id << 8) | (int)flags.LexicalEntry;
				else
				{
					int a = d.Daughters.Count;
					fid = ((int)ent.Id << 16) | (a << 8) | (int)flags.Rule;
					if (ent is LexicalRule)
						fid |= (int)flags.Lexical;
				}

				if (d.HasRootMatches())
					fid |= (int)flags.RootMatches;
				else if (d.IsValidRoot())
					fid |= (int)flags.RootMatch;
				return fid;
			}

			bool f_root_matches { get { return ((flags)flags_arity_id & flags.RootMatches) != 0; } }
			bool f_root_match { get { return ((flags)flags_arity_id & flags.RootMatch) != 0; } }
			public bool f_redirect { get { return ((flags)flags_arity_id & flags.Redirect) != 0; } }

			public int record_size
			{
				get
				{
					if (((flags)flags_arity_id & flags.Redirect) != 0)
						return sizeof(redirect);
					if (((flags)flags_arity_id & flags.RootMatches) != 0)
					{
						fixed (dnode* pt = &this)
							return sizeof(rootmatches) + ((dnode.rootmatches*)pt)->c_rm * sizeof(int);
					}
					if (((flags)flags_arity_id & flags.RootMatch) != 0)
						return sizeof(rootmatch);
					return sizeof(dnode);
				}
			}


			public static void Write(BinaryWriter bw, IDerivation d)
			{
				int fid = _make_fid(d);
				bw.Write(fid);
				//bw.Write(d.Id);

				if (d.HasRootMatches())
				{
					var rgss = d.MatchedStartSymbols.ToArray();
					bw.Write(rgss.Length);
					foreach (var ss in rgss)
						bw.Write(ss._id);
				}
				else
				{
					//Debug.Assert((((flags)fid & flags.RootMatch) != 0) == d is IDerivation);
					if (d.IsValidRoot())
						bw.Write(d.ItemStartSymbol._id);
				}
			}

			public static void Next(ref dnode* pt)
			{
				pt = (dnode*)((byte*)pt + pt->record_size);
			}

			//public flags EntryType { get { return (flags)flags_arity_id & flags._EntryTypeMask; } }
			public static flags get_obj_type(flags bflags)
			{
				if ((bflags & flags.Redirect) != 0)
					throw new Exception(String.Format("ZZ {0} {1:X2}", bflags, (byte)bflags));

				if ((bflags & dnode.flags.RootMatches) != 0)
					return dnode.flags.RootMatches;
				if ((bflags & dnode.flags.RootMatch) != 0)
					return dnode.flags.RootMatch;
				return bflags & flags._EntryTypeMask;
			}

			public static int _get_arity(DerivationStore ds, uint offs)
			{
				fixed (byte* pb = &ds.SafeBuf[offs])
					return ((dnode*)pb)->arity;
			}
			public static bool _f_redirect(DerivationStore ds, uint offs)
			{
				fixed (byte* pb = &ds.SafeBuf[offs])
					return ((dnode*)pb)->f_redirect;
			}
			public static int _rmx_count(DerivationStore ds, uint offs)
			{
				fixed (byte* pb = &ds.SafeBuf[offs])
					return ((dnode.rootmatches*)pb)->c_rm;
			}

			//public static uint _redirect(DerivationStore ds, uint offs)
			//{
			//    fixed (byte* pb = ds.SafeBuf)
			//    {
			//        while (true)
			//        {
			//            uint j = *(uint*)(pb + offs);
			//            if (((dnode.flags)j & dnode.flags.Redirect) == 0)
			//                return j >> 8;
			//            offs >>= 8;
			//        }
			//    }
			//}

			public int arity
			{
				get
				{
					if (f_redirect)
						return 0;

					if (((flags)flags_arity_id & flags._EntryTypeMask) == flags.LexicalEntry)
						return 0;
					return (byte)(flags_arity_id >> 8);
				}
			}

			public static IChartLicense License(DerivationStore ds, uint offs)
			{
				uint fai;
				fixed (byte* pb = &ds.SafeBuf[offs])
					fai = ((dnode*)pb)->flags_arity_id;

				if (((flags)fai & flags.Redirect) != 0)
					throw new Exception();

				//hacky, fix later
				var em = ds.em;
				flags et = (flags)fai & flags._EntryTypeMask;
				int sub_ix = (int)(fai >> (et == flags.LexicalEntry ? 8 : 16));
				if (et == flags.LexicalEntry)
					return em.lex.LexicalEntries[sub_ix];
				if (et == flags.LexicalEntryGeneric)
					return em.lex.GenericLexicalEntries[sub_ix];
				if (et == flags.LexicalRule)
					return em._lexical_rules[sub_ix];
				if (et == flags.SyntaxRule)
					return em._syntax_rules[sub_ix];
				throw new Exception("unknown Entry type in compact derivation");
			}

			public static StartSymbol _rootmatch_start_sym(DerivationStore ds, uint offs)
			{
				int ss_id;
				fixed (byte* pb = &ds.SafeBuf[offs])
				{
					rootmatch* pt = (rootmatch*)pb;
					Debug.Assert(((dnode*)pt)->f_root_match);
					Debug.Assert(!((dnode*)pt)->f_redirect);
					ss_id = pt->ss_id;
				}
				return ds.em._start_symbols[Instance._get_sub_index(ss_id)];
			}
			public static StartSymbol _rootmatches_start_syms(DerivationStore ds, uint offs, int ix)
			{
				fixed (byte* pb = &ds.SafeBuf[offs])
				{
					int ss_id;
					rootmatches* pt = (rootmatches*)pb;
					Debug.Assert(((dnode*)pt)->f_root_matches);
					Debug.Assert(!((dnode*)pt)->f_redirect);
					if (ix >= pt->c_rm)
						return null;

					ss_id = ((int*)&pt->c_rm)[ix + 1] & 0x00FFFFFF;
					return ds.em._start_symbols[ss_id];
				}
			}

			public static StartSymbol _rootmatches_start_sym(DerivationStore ds, uint offs, Tfs tfs)
			{
				fixed (byte* pb = &ds.SafeBuf[offs])
				{
					rootmatches* pt = (rootmatches*)pb;
					Debug.Assert(((dnode*)pt)->f_root_matches);
					Debug.Assert(!((dnode*)pt)->f_redirect);

					int* piss = ((int*)&pt->c_rm) + 1;
					for (int i = 0; i < pt->c_rm; i++, piss++)
					{
						if (*piss < 0)
							return ds.em._start_symbols[*piss & 0x00FFFFFF];
					}

					piss = ((int*)&pt->c_rm) + 1;
					for (int i = 0; i < pt->c_rm; i++, piss++)
					{
						int ss_id = *piss & 0x00FFFFFF;
						StartSymbol ss = ds.em._start_symbols[ss_id];
						if (ds.em.fsu.UnifyCheck(ss.Expanded, tfs))
						{
							*piss |= unchecked((int)0x80000000);
							return ss;
						}
					}
					return null;
				}
			}
		};

		sealed class _list_realizer : _list_realizer<IDerivation>, IReadOnlyList<_cdrv_base>
		{
			public _list_realizer(DerivationStore ds, IList<uint> arr)
				: base(ds, arr)
			{
			}

			//void ICollection<_cdrv_base>.Add(_cdrv_base item) { throw not.impl; }
			//void ICollection<_cdrv_base>.Clear() { throw not.impl; }
			//void IList<_cdrv_base>.Insert(int index, _cdrv_base item) { throw not.impl; }
			//void IList<_cdrv_base>.RemoveAt(int index) { throw not.impl; }
			//bool ICollection<_cdrv_base>.Remove(_cdrv_base item) { throw not.impl; }

			//_cdrv_base IList<_cdrv_base>.this[int index]
			//{
			//	get { return (_cdrv_base)this[index]; }
			//	set { throw not.impl; }
			//}

			//int IList<_cdrv_base>.IndexOf(_cdrv_base item) { throw not.impl; }
			//bool ICollection<_cdrv_base>.Contains(_cdrv_base item) { throw not.impl; }
			//void ICollection<_cdrv_base>.CopyTo(_cdrv_base[] array, int arrayIndex)
			//{
			//}

			IEnumerator<_cdrv_base> IEnumerable<_cdrv_base>.GetEnumerator()
			{
				foreach (IDerivation dtr in this)
					yield return (_cdrv_base)dtr;
			}

			_cdrv_base IReadOnlyList<_cdrv_base>.this[int index]
			{
				get { return (_cdrv_base)this[index]; }
			}
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// daughter list deferred realizer for compact derivations
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//[DebuggerTypeProxy(typeof(_cdrv_list_debugger_type_proxy))]
		//[DebuggerDisplay("foo3")]
		class _list_realizer<T> : _ro_list_base<T>, IList<T>, ICollection where T : IDerivation
		{
			public _list_realizer(DerivationStore ds, IList<uint> arr)
			{
				if (ds == null || arr.Count == 0)
					throw new Exception();
				this.ds = ds;
				this.arr = arr as uint[] ?? arr.ToArray();
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			readonly DerivationStore ds;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public
			readonly uint[] arr;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int Count { get { return arr.Length; } }

			public T this[int index]
			{
				get { return (T)ds._get(arr[index]); }
				set { throw new InvalidOperationException(); }
			}

			public void CopyTo(T[] array, int arrayIndex)
			{
				foreach (uint o in arr)
					array[arrayIndex++] = (T)ds._get(o);
			}

			public IEnumerator<T> GetEnumerator()
			{
				foreach (uint o in arr)
					yield return (T)ds._get(o);
			}

			IEnumerator IEnumerable.GetEnumerator()
			{
				foreach (uint o in arr)
					yield return ds._get(o);
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public T[] _dbg_nodes { get { return arr.Select(offs => ds._get(offs)).Cast<T>().ToArray(); } }

			public int IndexOf(T item) { throw not.impl; }
			public bool Contains(T item) { throw not.impl; }
#if DEBUG
			[DebuggerDisplay("foox")]
			public class _cdrv_list_debugger_type_proxy
			{
				public _cdrv_list_debugger_type_proxy(_list_realizer l)
				{
					this.l = l;
				}
				[DebuggerBrowsable(DebuggerBrowsableState.Never)]
				_list_realizer l;

				[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
				_cdrv_base[] _dtrs
				{
					get { return l.arr.Select(offs => (_cdrv_base)l.ds._get(offs)).ToArray(); }
				}
			};
#endif
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerDisplay("{ToString(),nq}")]
		//[DebuggerTypeProxy(typeof(DerivationDebuggerTypeProxy))]
		//[DebuggerDisplay("offs: {offs} {ChartLicense}")]
		class _cdrv_base : identity_base,
#if WR
 WeakReference,
#endif
 IDerivation//, IEquatable<_cdrv_base>
		{
			public _cdrv_base(DerivationStore ds, uint offs)
				: base(ds)
#if WR
				: base(null)
#endif
			{

				this.ds = ds;
				this.offs = offs;
			}
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			protected readonly DerivationStore ds;

#if CACHE
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			internal _cdrv_base next;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			internal int last_access;
#endif
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			readonly internal uint offs;

			//[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public IReadOnlyList<IDerivation> Daughters
			{
				get
				{
					fixed (byte* pb = &ds.SafeBuf[offs])
					{
						if (((dnode*)pb)->f_redirect)
							throw new Exception();
						if (((dnode*)pb)->arity == 0)
							return Collection<IDerivation>.None;
					}
					return new _list_realizer(ds, ds._dtr_finder(offs));
				}
			}

			///////////////////////////////////////////////////////////////////////
			/// 
			public Tfs DerivationTfs()
			{
				if (this is _cdrv_lexent)
					return ((LexicalEntry)dnode.License(ds, offs)).Expanded;
#if WR
					Tfs _tfs = (Tfs)base.Target;
					if (_tfs == null)
						base.Target = _tfs = this.reconstitute_tfs(this, ds.g.Unifier);
					return _tfs;
#else
				Tfs tfs;
				if (pwt.FirstClaim())
				{
					try
					{
						tfs = this.reconstitute_tfs(ds.em.fsu.TfsUnifier);
						pwt.SetResult(tfs);
					}
					catch (Exception ex)
					{
						pwt.SetResult(null);
						throw ex;
					}
				}
				else
					tfs = pwt.Result;
				//if ((tfs = pwt.Result) == null)
				//jctrl.ThrowIfCancelled();
				return tfs;
#endif
			}
#if !WR
			MemoizedItem<Tfs> pwt;
#endif
			/// 
			///////////////////////////////////////////////////////////////////////

			///////////////////////////////////////////////////////////////////////
			/// 
			//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			//public long Id { get { fixed (byte* pb = &ds.SafeBuf[offs]) return ((dnode*)pb)->seq_id; } }
			/// 
			///////////////////////////////////////////////////////////////////////


			///////////////////////////////////////////////////////////////////////
			/// 
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public IChartLicense ChartLicense { get { return dnode.License(ds, offs); } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Type InstanceType { get { return ChartLicense.InstanceType; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public ulong DerivationHash { get { return this.HashCompute(); } }
			///
			public String ToString(bool f_color) { return this.ToString(f_color); }
			public override String ToString()
			{
				String s = offs.ToString("X4");
				if (ChartLicense is LexicalEntry)
					s += " lex";
				if (this.IsValidRoot())
					s += " root";
#if WR
				s += base.IsAlive ? " tfs+" : " tfs-";
#endif
				s += " arity-" + dnode._get_arity(ds, offs).ToString();
				s += " " + ChartLicense.Name;
				//if (ds != null)
				//    s += " " + DerivationHelper.ToString(this, false);
				return s;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			Double score;
			public Double Score(MaxEntModel model)
			{
				return !Double.IsNaN(score) ? score : (score = DerivationFuncs.Score(this, model));
			}
			public Double ParseSelectionScore { get { return Score(null); } }
			/// 
			///////////////////////////////////////////////////////////////////////

#if DEBUG
			public class DerivationDebuggerTypeProxy
			{
				public DerivationDebuggerTypeProxy(_cdrv_base d)
				{
					this.d = d;
				}
				[DebuggerBrowsable(DebuggerBrowsableState.Never)]
				_cdrv_base d;

				[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
				[DebuggerDisplay("PROXY")]
				public _cdrv_base[] _dbg
				{
					get
					{
						if (dnode._get_arity(d.ds, d.offs) == 0)
							return Collection<_cdrv_base>.None;
						return ((_list_realizer)d.Daughters).arr.Select(offs => (_cdrv_base)d.ds._get(offs)).ToArray();
					}


					//get { return (IList<_cdrv_base>)d.Daughters; }
				}
			};
#endif

			//public bool Equals(_cdrv_base other)
			//{
			//    return this.ds == other.ds && this.offs == other.offs;
			//}

			//public override bool Equals(object obj)
			//{
			//    var oo = obj as _cdrv_base;
			//    return oo != null && this.ds == oo.ds && this.offs == oo.offs;
			//}
			//public override int GetHashCode()
			//{
			//    return ds.GetHashCode() ^ (int)offs;
			//}


			public virtual StartSymbol[] MatchedStartSymbols
			{
				get { throw new NotImplementedException(); }
			}

			public virtual StartSymbol ItemStartSymbol
			{
				get { throw new NotImplementedException(); }
			}
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//[DebuggerTypeProxy(typeof(_cdrv_base.DerivationDebuggerTypeProxy))]
		[DebuggerDisplay("{ToString(),nq}")]
		sealed class _cdrv_lexent : _cdrv_base, ILexeme
		{
			public _cdrv_lexent(DerivationStore ds, uint offs)
				: base(ds, offs)
			{
			}

			public EntryMgr EntryMgr { get { return this.ds.em; } }

			public long Id { get { fixed (byte* pb = &ds.SafeBuf[offs]) return ((dnode*)pb)->seq_id; } }

			public int DaughterArity { get { return 0; } }
			public string Name { get { throw not.impl; } set { throw not.impl; } }
			Tfs IInstance.Expanded { get { throw not.impl; } }
			Tfs IInstance.Definition { get { throw not.impl; } }

			public String ReadbackTokensForm(ITfsSlot ts) { throw not.impl; }
			public String ReferenceForm { get { throw not.impl; } }
			public ITokenizer Tokenizer { get { throw not.impl; } set { throw not.impl; } }
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//[DebuggerTypeProxy(typeof(_cdrv_base.DerivationDebuggerTypeProxy))]
		[DebuggerDisplay("{ToString(),nq}")]
		sealed class _cdrv_rootmatch : _cdrv_base, IDerivation
		{
			public _cdrv_rootmatch(DerivationStore ds, uint offs)
				: base(ds, offs)
			{
			}

			public override StartSymbol ItemStartSymbol
			{
				get { return dnode._rootmatch_start_sym(ds, offs); }
			}
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		sealed class _cdrv_rootmatches : _cdrv_base, IDerivation
		{
			public _cdrv_rootmatches(DerivationStore ds, uint offs)
				: base(ds, offs)
			{
			}

			public override StartSymbol[] MatchedStartSymbols
			{
				get
				{
					int ix = 0;
					StartSymbol ss;
					StartSymbol[] ss_matches = null;
					while ((ss = dnode._rootmatches_start_syms(ds, offs, ix++)) != null)
						alib.Array.arr.Append(ref ss_matches, ss);
					return ss_matches;
				}
			}

			public override StartSymbol ItemStartSymbol
			{
				get
				{
					throw not.impl;
					//return MatchedStartSymbols.First();
				}
			}

			//public bool Validate()
			//{
			//	Tfs mdtfs = base.DerivationTfs();
			//	return mdtfs != null && dnode._rootmatches_start_sym(ds, offs, mdtfs) != null;
			//}
		};
	};
}
